//给定一个放有字母和数字的数组，找到最长的子数组，且包含的字母和数字的个数相同。 
//
// 返回该子数组，若存在多个最长子数组，返回左端点下标值最小的子数组。若不存在这样的数组，返回一个空数组。 
//
// 示例 1： 
//
// 
//输入：["A","1","B","C","D","2","3","4","E","5","F","G","6","7","H","I","J","K",
//"L","M"]
//
//输出：["A","1","B","C","D","2","3","4","E","5","F","G","6","7"]
// 
//
// 示例 2： 
//
// 
//输入：["A","A"]
//
//输出：[]
// 
//
// 提示： 
//
// 
// array.length <= 100000 
// 
//
// Related Topics 数组 哈希表 前缀和 👍 198 👎 0


package LeetCode.editor.cn;

import java.util.HashMap;
import java.util.Map;

/**
 * @author ldltd
 * @date 2025-09-12 22:21:09
 * @description 面试题 17.05. 字母与数字
 */
public class FindLongestSubarrayLcci{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 FindLongestSubarrayLcci fun=new FindLongestSubarrayLcci();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
public class Solution {
		 // 方法一：前缀和 + 哈希表
	public String[] findLongestSubarray1(String[] array) {
		Map<Integer, Integer> firstOccurrence = new HashMap<>();
		firstOccurrence.put(0, -1); // 初始前缀和为0

		int prefixSum = 0;
		int maxLength = 0;
		int start = -1, end = -1;

		for (int i = 0; i < array.length; i++) {
			// 字母记为-1，数字记为+1
			prefixSum += Character.isDigit(array[i].charAt(0)) ? 1 : -1;
			// 找到当前前缀和第一次出现的位置
			if (firstOccurrence.containsKey(prefixSum)) {
				int prevIndex = firstOccurrence.get(prefixSum);
				int currentLength = i - prevIndex;
				if (currentLength > maxLength) {
					maxLength = currentLength;
					start = prevIndex + 1;
					end = i;
				}
			} else {
				firstOccurrence.put(prefixSum, i);
			}
		}

		if (maxLength == 0) {
			return new String[0];
		}

		String[] result = new String[maxLength];
		System.arraycopy(array, start, result, 0, maxLength);
		return result;
	}
}

//leetcode submit region end(Prohibit modification and deletion)

}
